package com.algorithms.techniques;


public class OptimalBST
{
	double[][] estimatedCost = null;
	double[][] depthCost  = null;
	int[][] root  = null;
	int totalKeys=0;
	int arraySize=0;
	public OptimalBST(int n)
	{
		 totalKeys=n;
		 arraySize=totalKeys+1;
		 estimatedCost = new double[arraySize][arraySize];
		 depthCost = new double[arraySize][arraySize];
		 root = new int[totalKeys][totalKeys];
	}
	private static int INFINITY =99999999;
	
	public void optimalBST(double[] probability)
	{
		
		estimatedCost[0][0]=0;
		for(int i=1;i< arraySize ;i++)
		{
			estimatedCost[i][i-1]=0;
			depthCost[i][i-1]=0;
		}
		for(int length=1; length<totalKeys;length++ )
		{
			for(int i=0;i< arraySize -length+1 ;i++)
			{
				int j =i+ length;
				depthCost[i][j]=depthCost[i][j-1]+probability[j-1];
				          
				chooseRootAndCalcuateCost( i, j);
			}
		}
	}
	private void chooseRootAndCalcuateCost(int i,int j)
	{
		for(int r=i;r<j;r++)
		{
			double temp=estimatedCost[i][r] +estimatedCost[r+1][j]+depthCost[i][j];
			if(temp<estimatedCost[i][j])
			{
				estimatedCost[i][j]=temp;
				root[i][j]=r;
			}
		}
	}
	
	public int[][] getRoot()
	{
		return root;
	}
	
	public void constructOptimalBST()
	{
	    
		int r = root[0][totalKeys-1];
		System.out.println("root-" +r);
		constructOptimalBSTSubtree(0, r-1, r, "left");
		constructOptimalBSTSubtree(r + 1, totalKeys-1, r, "right");
		
	}
	
	private void constructOptimalBSTSubtree(int i, int j, int r, String dir)
	{
		if( i <= j)
		{
		  int t = root[i][j];
		  System.out.println(t + "is " + dir + " child of " +r);
		  constructOptimalBSTSubtree(i, t-1, t, "left");
		  constructOptimalBSTSubtree(t + 1, j, t, "right");
		}
	}
}
